// 给定一个整数数组nums和一个整数k
// 要求：找到该数组中和为k的连续子数组的个数

// 解题思路
// 先用一重循环遍历数组，计算出数组nums中前i个元素的和，保存到一维数组pre_sum中，那么对于任意[j, i]的子数组的和为pre_sum[i] - pre_sum[j-1]
// 由于我们只关心和为k出现的次数，不关心具体的解，可以使用哈希表来加速运算
// pre_sum[i]的定义是前i个元素和，则pre_sum[i]可以由pre_sum[i-1]递推而来，即:pre_sum[i] = pre_sum[i-1] + num[i]
// [j,i]子数组和为k，可以转换为：pre_sum[i] - pre_sum[j - 1] === k
// 所以当我们考虑以i结尾和为k的连续子数组个数时，只需要统计有多少个前缀和为pre_sum[i] - k的个数即可：
// 1. 使用pre_sum记录前缀和
// 2. 使用哈希表pre_dic记录pre_sum[i]出现的次数，键值对为pre_sum[i] : pre_sum_count
// 3. 从左到右遍历数组，计算当前前缀和pre_sum
// 4. 如果pre_sum-k在哈希表中，则答案个数累加，pre_dic[pre_sum-k]
// 5. 如果pre_sum在哈希表中，则前缀和个数累加1，即pre_dic[pre_sum] += 1
// 6. 最后输出答案个数

function subarraySum(nums, k) {
    let sumMap = new Map
    sumMap.set(0, 1)
    let preSum = 0
    let count = 0
    for (let i = 0; i < nums.length; i++) {
        // 求前缀和
        preSum += nums[i]
        if (sumMap.has(preSum - k)) {
            count += sumMap.get(preSum - k)
        }     
        if (sumMap.has(preSum)) {
            sumMap.set(preSum, sumMap.get(preSum) + 1)
        } else {
            sumMap.set(preSum, 1)
        }
    }
    return count
}
let nums = [1, 2, 3, 0, 1, 2], k = 3
console.log(subarraySum(nums, k))